/*
 * @Description: In User Settings Edit
 * @Author: your name
 * @Date: 2019-08-23 08:40:52
 * @LastEditTime: 2019-08-23 10:02:46
 * @LastEditors: Please set LastEditors
 */
/*
 * @lc app=leetcode.cn id=16 lang=javascript
 *
 * [16] 最接近的三数之和
 *
 * https://leetcode-cn.com/problems/3sum-closest/description/
 *
 * algorithms
 * Medium (41.48%)
 * Likes:    233
 * Dislikes: 0
 * Total Accepted:    37.6K
 * Total Submissions: 90.7K
 * Testcase Example:  '[-1,2,1,-4]\n1'
 *
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target
 * 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * 
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 * 
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 * 
 * 
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums = nums.sort((a,b)=>{return a-b})
    const len = nums.length
    var result


    for(let i=0;i<len;i++){
        let l = 0
        let r = len - 1
        while(l < r){
            if( l == i){l++;continue}
            if( r == i){r--;continue}

            const step = nums[i]+nums[l]+nums[r]
            if(step == target) return step

            step<target?l++:r--

            if(result == null){
                result = step
            }else{
                result = Math.abs(result - target) > Math.abs(step - target)?step : result
            }
            
            
        }
    }

    return result
};

